#include <iostream>
#include "./util/shortest-path.h"

using namespace std;

int main()
{
	MGraph graph;
	createGraph(graph, UN_DIRECT, TYPE_NET);
	insertVex(graph, '0');
	insertVex(graph, '1');
	insertVex(graph, '2');
	insertVex(graph, '3');
	insertVex(graph, '4');
	insertVex(graph, '5');
	insertVex(graph, '6');
	insertVex(graph, '7');
	insertVex(graph, '8');
	insertArc(graph, 0, 1, 1);
	insertArc(graph, 0, 2, 5);
	insertArc(graph, 1, 2, 3);
	insertArc(graph, 1, 3, 7);
	insertArc(graph, 1, 4, 5);
	insertArc(graph, 2, 4, 1);
	insertArc(graph, 2, 5, 7);
	insertArc(graph, 3, 4, 2);
	insertArc(graph, 4, 5, 3);
	insertArc(graph, 3, 6, 3);
	insertArc(graph, 4, 6, 6);
	insertArc(graph, 4, 7, 9);
	insertArc(graph, 5, 7, 5);
	insertArc(graph, 6, 7, 2);
	insertArc(graph, 6, 8, 7);
	insertArc(graph, 7, 8, 4);
	printGraph(graph);
	int pathArc[graph.vexNum], shortTable[graph.vexNum];
	dijkstra(graph, 0, pathArc, shortTable);
	cout << "最短路径前驱：";
	for (int i = 0; i < graph.vexNum; i++)
	{
		cout << pathArc[i] << " ";
	}
	cout << endl
		 << "最短路径长度：";
	for (int i = 0; i < graph.vexNum; i++)
	{
		cout << shortTable[i] << " ";
	}
}